{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #组合总和 Ⅳ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combinationSum4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合总和 Ⅳ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由 <strong>不同</strong>&nbsp;正整数组成的数组 <code>nums</code> ，和一个目标整数 <code>target</code> 。请从 <code>nums</code> 中找出并返回总和为 <code>target</code> 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。</p>\n",
    "\n",
    "<p>题目数据保证答案符合 32 位整数范围。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], target = 4\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>\n",
    "所有可能的组合为：\n",
    "(1, 1, 1, 1)\n",
    "(1, 1, 2)\n",
    "(1, 2, 1)\n",
    "(1, 3)\n",
    "(2, 1, 1)\n",
    "(2, 2)\n",
    "(3, 1)\n",
    "请注意，顺序不同的序列被视作不同的组合。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [9], target = 3\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>nums</code> 中的所有元素 <strong>互不相同</strong></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 377&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/combination-sum-iv/\">https://leetcode-cn.com/problems/combination-sum-iv/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [D0F0SV](https://leetcode.cn/problems/D0F0SV/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [D0F0SV](https://leetcode.cn/problems/D0F0SV/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n4', '[9]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0 for i in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # @cache\n",
    "        # def dfs(target):\n",
    "        #     if not nums or target<0: return 0\n",
    "        #     mem = set()\n",
    "        #     res = 0\n",
    "        #     for v in nums:\n",
    "        #         if v in mem: continue\n",
    "        #         if v==target: \n",
    "        #             res+=1\n",
    "        #             continue\n",
    "        #         res += dfs(target-v)\n",
    "        #         mem.add(v)\n",
    "        #     return res\n",
    "        # return dfs(target)\n",
    "\n",
    "        nums.sort()\n",
    "        dp = [0]*(target+1)\n",
    "        for i in range(target+1):\n",
    "            if i in nums:\n",
    "                dp[i]=1\n",
    "        for i in range(target+1):\n",
    "            for v in nums:\n",
    "                if v>i: break\n",
    "                dp[i] += dp[i-v]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1 + abs(min(nums))) # 包含负数的情况下 + abs(min(nums)), 防止越界\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1): # 为什么先遍历nums, 结果是错误的?\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target] # 包含负数的情况不能返回dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[1]+[0]*(target)\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i>=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "                    #print(dp)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for j in range(1, target + 1):\n",
    "            for i in range(0, len(nums)):\n",
    "                if j >= nums[i]:\n",
    "                    dp[j] += dp[j - nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for j in range(0, target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if (j - nums[i] >= 0):\n",
    "                    dp[j] = dp[j] + dp[j - nums[i]]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1] + [0] * target\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0 for _ in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if i>=j:\n",
    "                   dp[i]=dp[i]+dp[i-j]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + abs(min(nums)) + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1): # 为什么先遍历nums, 结果是错误的?\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i-num >= 0:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for j in range(0, target + 1):\n",
    "            for i in range(0, len(nums)):\n",
    "                if j >= nums[i]:\n",
    "                    dp[j] += dp[j - nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "    dp = [1] + [0 for i in range(target)]\n",
    "\n",
    "    for i in range(1, target + 1):\n",
    "      for num in nums:\n",
    "        if i - num >= 0: dp[i] += dp[i - num]\n",
    "    \n",
    "    return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for j in range(target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if j-nums[i]>=0:\n",
    "                    dp[j] += dp[j-nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1]+[0]*target\n",
    "        for i in range(target):\n",
    "            if dp[i] == 0: continue\n",
    "            for n in nums:\n",
    "                if i+n <= target: dp[i+n] += dp[i]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        f = [0] * (target+1)\n",
    "        f[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    f[i] += f[i-num]\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i>= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        #dp[i][j]代表 0-i个数组成j的个数\n",
    "        dp=[0 for _ in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for n in nums:\n",
    "                if i>=n:\n",
    "                  dp[i]+=dp[i-n]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# res = 0\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # res = 0\n",
    "        dp = [0]*(target+2)\n",
    "\n",
    "        use = []\n",
    "        for tmp in nums:\n",
    "            if tmp <= target:\n",
    "                use.append(tmp)\n",
    "        for tmp in use:\n",
    "            dp[tmp+1]=1\n",
    "\n",
    "        for i in range(target+2):\n",
    "            for tmp in use:\n",
    "                if i-tmp>0 and dp[i-tmp]>0:\n",
    "                    dp[i]=dp[i-tmp]+dp[i]\n",
    "        \n",
    "        return dp[target+1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num>=0:dp[i]+=dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        if target == 0:\n",
    "            return 1\n",
    "        if min(nums) > target:\n",
    "            return 0\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1] + [0] * target\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i - num]\n",
    "        \n",
    "        return dp[target]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        f = [0] * (target + 1)\n",
    "        f[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    f[i] += f[i - num]\n",
    "        return f[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        nums.sort()\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "                \n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # 完全背包，排列\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for j in range(target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if j < nums[i]:\n",
    "                    continue\n",
    "                dp[j] += dp[j-nums[i]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for j in range(1,target+1):\n",
    "            for i in range(n):\n",
    "                if nums[i]<=j:dp[j]+=dp[j-nums[i]]\n",
    "        #组合问题 1、2和2、1相同，先遍历物品再遍历容量，这样出现了3，1，2不会再出现3，2，1\n",
    "        #排列问题 1、2和2、1不同，先遍历容量再遍历物品\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            dp[i] += sum(dp[i-num] for num in nums if i-num>=0)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        dp[0] = 1\n",
    "\n",
    "        for t in range(1, target+1):\n",
    "            # 由于nums元素各不相同\n",
    "            # 在newTarget基础上增加一个num，组合方式一定各不相同\n",
    "            for num in nums:\n",
    "                if t - num < 0:\n",
    "                    break\n",
    "                else:\n",
    "                    newTarget = t - num\n",
    "                    dp[t] += dp[newTarget]\n",
    "        \n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range (1,target+1):\n",
    "            for k in nums:\n",
    "                if k<=i:\n",
    "                    dp[i]=dp[i]+dp[i-k]\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        # f(i)表示走到第i个台阶需要走多少步\n",
    "        # 范围 target + 1\n",
    "        # dp = []*(target+1)\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for j in range(len(nums)):\n",
    "                if (i-nums[j])>= 0 :\n",
    "                    dp[i] += dp[i-nums[j]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        #容量为target的完全背包\n",
    "        #dp[j] += dp[j-nums[i]]\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] =1\n",
    "        for j in range(1,target+1):#\n",
    "            for i in nums:\n",
    "                if j-i >= 0:\n",
    "                    dp[j] +=dp[j-i]\n",
    "                          \n",
    "        return dp[target]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for i in range(1, target + 1):\n",
    "            for n in nums:\n",
    "                if i >= n:\n",
    "                    dp[i] += dp[i - n]\n",
    "                    \n",
    "        return dp[target]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + abs(min(nums)) + 1) # 包含负数的情况\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1): # 为什么先遍历nums, 结果是错误的?\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target] # 包含负数的情况不能返回dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if i-j>=0:\n",
    "                    dp[i]+=dp[i-j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for j in range(n):\n",
    "                if(i>=nums[j]):\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i] += dp[i-nums[j]]\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*(target+1)\n",
    "        for j in range(n):\n",
    "            if nums[j]<=target:\n",
    "                dp[nums[j]] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for j in range(n):\n",
    "                if i>=nums[j]:\n",
    "                    dp[i] += dp[i-nums[j]]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for c in nums:\n",
    "                if c <= i:\n",
    "                    dp[i] += dp[i-c]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num>=0:dp[i]+=dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # 如果有负数我就不能dp了啊 麻了 看了一眼有负数的解决方案是直接截断\n",
    "        dp = [0 for i in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] = dp[i] + dp[i-num]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        mem = {}\n",
    "\n",
    "        def backtrack(target):\n",
    "            if target in mem:\n",
    "                return mem[target]\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                if nums[i] < target:\n",
    "                    ans += backtrack(target - nums[i])\n",
    "                elif nums[i] == target:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    break\n",
    "            mem[target] = ans\n",
    "            return ans\n",
    "\n",
    "        return backtrack(target)\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0 for i in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1] + [0] * target\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i - num]\n",
    "        \n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num>=0:dp[i]+=dp[i-num]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # 状态转移方程 dp[i] += dp[i-nums[j]]\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if j <= i:\n",
    "                    dp[i] += dp[i-j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#组合总和 Ⅳ,输入：nums = [1,2,3], target = 4,输出：7,所有可能的组合为：(1, 1, 1, 1)\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num<=i:dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        num=len(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            res=0\n",
    "            if s==target:\n",
    "                res+=1\n",
    "                \n",
    "            for i in range(num):\n",
    "                if nums[i]+s<=target:\n",
    "                    res+=dfs(s+nums[i])\n",
    "            return res\n",
    "        res=dfs(0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        # dp[i]:nums构成综合为i的排列个树\n",
    "        dp  = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1,1):\n",
    "            for j in range(0,i,1):\n",
    "                if i-j in nums:\n",
    "                    dp[i] +=dp[j]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i == num:\n",
    "                    dp[i] += 1\n",
    "                dp[i] += dp[max(0, i-num)]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i == num:\n",
    "                    dp[i] += 1\n",
    "                dp[i] += dp[max(0, i-num)]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num<=i:dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          if i == target:\n",
    "             return 1\n",
    "          res = 0\n",
    "          for num in nums:\n",
    "             if num + i <= target:\n",
    "                res += dfs(i + num)\n",
    "          return res\n",
    "       return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                dp[i] += (i >= num and dp[i - num])\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 动态规划\n",
    "        # dp = [0] * (target + 1)\n",
    "        # dp[0] = 1\n",
    "        # for i in range(1, target + 1):\n",
    "        #     for num in nums:\n",
    "        #         dp[i] = dp[i] + (num <= i and dp[i - num])\n",
    "\n",
    "        # return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                dp[i] += (i >= num and dp[i - num])\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 动态规划\n",
    "        # dp = [0] * (target + 1)\n",
    "        # dp[0] = 1\n",
    "        # for i in range(1, target + 1):\n",
    "        #     for num in nums:\n",
    "        #         dp[i] = dp[i] + (num <= i and dp[i - num])\n",
    "\n",
    "        # return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        method = 'mine2'\n",
    "        if method == 'mine':\n",
    "            def dfs(comb, target):\n",
    "                if target < 0: return\n",
    "                if target == 0:\n",
    "                    res.append(comb[:])\n",
    "                for i in range(n):\n",
    "                    dfs(comb + [nums[i]], target - nums[i])\n",
    "\n",
    "            n = len(nums)\n",
    "            res = []\n",
    "            dfs([], target)\n",
    "            return len(res)\n",
    "\n",
    "        if method == 'mine2':\n",
    "            n = len(nums)\n",
    "            dp = [0] * ( target + 1 )\n",
    "            dp[0] = 1\n",
    "            for i in range(1, target + 1):\n",
    "                for j in range(n):\n",
    "                    if i >= nums[j]:\n",
    "                        dp[i] += dp[i - nums[j]]\n",
    "             \n",
    "\n",
    "            return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        #容量为target的完全背包\n",
    "        #dp[j] += dp[j-nums[i]]\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] =1\n",
    "        for j in range(1,target+1):#\n",
    "            for i in nums:\n",
    "                if j-i >= 0:\n",
    "                    dp[j] +=dp[j-i]\n",
    "                          \n",
    "        return dp[target]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(count=0):\n",
    "            if count>target:\n",
    "                return 0\n",
    "            ans=0\n",
    "            if count==target:\n",
    "                ans+=1\n",
    "            for j in nums:\n",
    "                if count+j<=target:\n",
    "                  ans+=dfs(count+j)\n",
    "            return ans\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        num=len(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            res=0\n",
    "            if s==target:\n",
    "                res+=1\n",
    "                \n",
    "            for i in range(num):\n",
    "                if nums[i]+s<=target:\n",
    "                    res+=dfs(s+nums[i])\n",
    "            return res\n",
    "        res=dfs(0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i < num:\n",
    "                    continue\n",
    "                dp[i] += dp[max(0, i-num)]\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        #nums.sort()\n",
    "        n=len(nums)\n",
    "        #path=[]\n",
    "        \n",
    "        # def dfs(i,c):\n",
    "            \n",
    "            \n",
    "\n",
    "        #     if i<0:\n",
    "        #         return 1 if c==0 else 0\n",
    "        #     # if c<nums[0]:\n",
    "        #     #     return 0\n",
    "            \n",
    "\n",
    "        #     if c<nums[i]:\n",
    "        #         return dfs(i-1,c)\n",
    "\n",
    "        #     return dfs(i-1,c)+dfs(i,c-nums[i])\n",
    "\n",
    "\n",
    "        # return dfs(n-1,target)\n",
    "        #path=[]\n",
    "        @cache\n",
    "        def dfs(c):\n",
    "\n",
    "            if c ==0:\n",
    "                return 1 \n",
    "           \n",
    "        \n",
    "\n",
    "            res=0\n",
    "            for j in range(n):\n",
    "                if c>=nums[j]:\n",
    "                    res+=dfs(c-nums[j])\n",
    "                   \n",
    "            return res\n",
    "\n",
    "        return  dfs(target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dp(x):\n",
    "            ans = 0\n",
    "            for number in nums:\n",
    "                if number == x:\n",
    "                    ans += 1\n",
    "                elif number < x:\n",
    "                    ans += dp(x - number)\n",
    "            return ans\n",
    "\n",
    "        return dp(target)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(tmp=0):\n",
    "            ans = 0\n",
    "            if tmp == target:\n",
    "                ans += 1\n",
    "            for each in nums:\n",
    "                if each + tmp<= target:\n",
    "                    ans += dfs(tmp+each)\n",
    "            return ans\n",
    "        return dfs()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(target):\n",
    "            next_nums = []\n",
    "            for v in nums:\n",
    "                if v<=target: next_nums.append(v)\n",
    "            if not next_nums: return 0\n",
    "            mem = set()\n",
    "            res = 0\n",
    "            for v in next_nums:\n",
    "                if v in mem: continue\n",
    "                if v==target: \n",
    "                    res+=1\n",
    "                    continue\n",
    "                res += dfs(target-v)\n",
    "                mem.add(v)\n",
    "            return res\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(tmp=0):\n",
    "            ans = 0\n",
    "            if tmp == target:\n",
    "                ans += 1\n",
    "            for each in nums:\n",
    "                if each + tmp<= target:\n",
    "                    ans += dfs(tmp+each)\n",
    "            return ans\n",
    "        return dfs()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @functools.lru_cache(maxsize=None)\n",
    "        def sol(t) :\n",
    "            if t == 0 : return 1\n",
    "            return sum([sol(t-n) for n in nums if t-n >= 0])\n",
    "        return sol(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                res += dp(i-num)\n",
    "            return res\n",
    "        return dp(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(target):\n",
    "            if not nums or target<0: return 0\n",
    "            mem = set()\n",
    "            res = 0\n",
    "            for v in nums:\n",
    "                if v in mem: continue\n",
    "                if v==target: \n",
    "                    res+=1\n",
    "                    continue\n",
    "                res += dfs(target-v)\n",
    "                mem.add(v)\n",
    "            return res\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(total):\n",
    "            if total == 0:\n",
    "                return 1\n",
    "            elif total < 0:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "            for i in range(len(nums)):\n",
    "                ans += dp(total - nums[i])\n",
    "            return ans\n",
    "        return dp(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def solve(s):\n",
    "            if s == target:\n",
    "                return 1\n",
    "            if s > target:\n",
    "                return 0\n",
    "            c = 0\n",
    "            for n in nums:\n",
    "                c += solve(s + n)\n",
    "            return c\n",
    "        return solve(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(target):\n",
    "            if target==0:return 1\n",
    "            if target<0:return 0\n",
    "            return sum(dfs(target-i) for i in nums)\n",
    "        return dfs(target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
